package com.south.base.test.arithmetic.graph;

import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author Administrator
 * @date 2020/8/4 9:56
 */
public class Schedule {
    /**
     * 课程表
     * 你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。
     * 在选修某些课程之前需要一些先修课程。 
     * 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]
     */
    @Test
    public void canFinish() {
        Assert.assertTrue(canFinish(2, new int[][]{{1, 0}}));
        Assert.assertFalse(canFinish(2, new int[][]{{1, 0}, {0, 1}}));
        Assert.assertFalse(canFinish(3, new int[][]{{1, 0}, {2, 0}, {0, 2}}));
        Assert.assertFalse(canFinish(3, new int[][]{{1, 0}, {0, 2}, {2, 1}}));
        Assert.assertTrue(canFinish2(2, new int[][]{{1, 0}}));
        Assert.assertFalse(canFinish2(2, new int[][]{{1, 0}, {0, 1}}));
        Assert.assertFalse(canFinish2(3, new int[][]{{1, 0}, {2, 0}, {0, 2}}));
        Assert.assertFalse(canFinish2(3, new int[][]{{1, 0}, {0, 2}, {2, 1}}));
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] visited = new int[numCourses];
        Arrays.fill(visited, Integer.MAX_VALUE);
        for (int[] prerequisite : prerequisites) {
            if (!canFinish(visited, prerequisites, prerequisite[0])) {
                return false;
            }
        }
        return true;
    }

    public boolean canFinish(int[] visited, int[][] prerequisites, int i) {
        for (int[] prerequisite : prerequisites) {
            if (prerequisite[1] != i) {
                continue;
            }
            visited[i] = prerequisite[0];
            if (visited[prerequisite[0]] == Integer.MAX_VALUE && !canFinish(visited, prerequisites, prerequisite[0])) {
                return false;
            }
            if (visited[prerequisite[0]] >= 0) {
                return false;
            }
            visited[i] = -1;
        }
        visited[i] = -1;
        return true;
    }

    public boolean canFinish2(int numCourses, int[][] prerequisites) {
        // 先序扫描图，减少后续每次都续再次搜啊面全部课程的时间
        List<Integer>[] graph = new List[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] arr : prerequisites) {
            graph[arr[1]].add(arr[0]);
        }
        int[] visited = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if (visited[i] == 0 && !canFinish2(i, graph, visited)) {
                return false;
            }
        }
        return true;
    }

    private boolean canFinish2(int i, List[] graph, int[] visited) {
        visited[i] = 1;
        List<Integer> neighbours = graph[i];
        for (int j = 0; j < neighbours.size(); j++) {
            int neigh = neighbours.get(j);
            if (visited[neigh] == 1) {
                return false;
            }
            if (visited[neigh] == 0 && !canFinish2(neigh, graph, visited)){
                return false;
            }
        }
        visited[i] = 2;
        return true;
    }
}
